package _笔试._阿里巴巴._2021;

/**
 * @author： YHSimon
 * @date： 2022-08-20 16:07
 */
public class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() < 2) return 0;
        int res = 0;
        int[] dp=new int[s.length()];
        for(int i=1;i<s.length();i++){
            if(s.charAt(i)==')'){
                int preLen=dp[i-1];
                int pre=i-preLen-1;

                if(pre>=0&&s.charAt(pre)=='('){
                    dp[i]=dp[i-1]+2;
                    if(pre-1>=0){
                        dp[i]+=dp[pre-1];
                    }
                }
            }
            res=Math.max(res, dp[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.longestValidParentheses(")()()"));
    }
}
